/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

//@lint-ignore-every

#include <gtest/gtest.h>

#include "RedexResources.h"
#include "RedexTest.h"
#include "StringTreeSet.h"

struct StringTreeTest : public RedexTest {};

static std::string toHexRepresentation(const std::string& str) {
  std::ostringstream hex_str;
  for (char c : str) {
    hex_str << std::hex << std::setw(2) << std::setfill('0')
            << static_cast<int>(c);
  }
  std::string hex = hex_str.str();
  return hex;
}

TEST_F(StringTreeTest, testEncode) {
  std::vector<std::string> class_names = {
      "com.facebook.location.platform.api.LocationRequest",
      "com.facebook.contacts.picker.ContactPickerRowVisitor",
      "com.facebook.payments.checkout.configuration.model."
      "CheckoutTermsAndPolicies",
      "com.facebook.photos.albums.fragment.AlbumMediaPickerController",
      "com.facebookpay.msc.listsection.item.controller.DividerItemDataModel",
      "com.facebook.optic.util.ExifReader",
      "com.facebook.facecast.event.model.FacecastPromoEvent$Deserializer",
      "com.facebook.timeline.gemstone.overlay.LoggingOverlayAdapter$"
      "LoggingOverlayItemViewHolder",
      "com.facebook.storelocator.StoreLocatorCardProvider$2",
      "com.facebook.inspiration.avatars."
      "InspirationAvatarsBackgroundTopBarController$3",
      "com.facebook.contacts.model.PhonebookPhoneNumber",
      "com.facebook.keyframes.decoder.icons.IconDocument$KFSize",
      "com.facebook.nativetemplates.fb.action.eventopen.FBEventOpenAction",
      "com.facebook.pages.common.requesttime.calendar.components."
      "ServicesProfilePictureComponent",
      "com.facebook.account.switcher.nux.TargetedNuxResolver$1",
      "com.facebook.common.exceptionhandler."
      "UserInitiatedExpectedAppExitException",
      "com.facebook.rtc.logging.api.interfaces.RtcNotificationImpressionLog",
      "com.facebook.composer.ui.popover.CreationPopoverListView$ShowAnimation",
      "com.facebook.composer.audienceeducator.ComposerAudienceEducatorData$"
      "TagExpansionExplanationType",
      "com.facebook.messaging.business.customerfeedback.model."
      "CustomerFeedbackPageData",
      "com.facebook.messaging.customthreads.model.ThreadThemeInfo",
      "com.facebook.adinterfaces.AdInterfacesCouponInterstitialActivity",
      "com.facebook.audience.stories.highlights.settings.protocol."
      "FetchStoriesHighlightsSettingsGraphQLModels$"
      "StoriesHighlightsPrivacySettingsTreeModel$StoriesDataTreeModel$"
      "StoryHighlightPreferencesTreeModel"};

  std::string encoded = StringTreeSet::encode_string_tree_set(class_names);

  std::string hex = toHexRepresentation(encoded);

  EXPECT_EQ(
      hex,
      "636f6d2e66616365626f6f6b10032e70040c01100e61636c030166070601693c06016b7f"
      "06016c2c07016d5207016e4008016f760801700d090172550a01730e0b0174360b011004"
      "63647c010175300201636f756e742e73776974636865722e6e75782e5461726765746564"
      "4e75785265736f6c76657224310801696e74657266616365732e4164496e746572666163"
      "6573436f75706f6e496e7465727374697469616c416374697669747908016469656e6365"
      "2e73746f726965732e686967686c69676874732e73657474696e67732e70726f746f636f"
      "6c2e466574636853746f72696573486967686c696768747353657474696e677347726170"
      "68514c4d6f64656c732453746f72696573486967686c6967687473507269766163795365"
      "7474696e6773547265654d6f64656c2453746f7269657344617461547265654d6f64656c"
      "2453746f7279486967686c69676874507265666572656e636573547265654d6f64656c08"
      "016f10036d6e3f050110036d703704016f6e2e657863657074696f6e68616e646c65722e"
      "55736572496e69746961746564457870656374656441707045786974457863657074696f"
      "6e08016f7365722e100361750e0501756469656e63656564756361746f722e436f6d706f"
      "73657241756469656e63654564756361746f724461746124546167457870616e73696f6e"
      "4578706c616e6174696f6e547970650801692e706f706f7665722e4372656174696f6e50"
      "6f706f7665724c697374566965772453686f77416e696d6174696f6e080174616374732e"
      "10036d706705016f64656c2e50686f6e65626f6f6b50686f6e654e756d62657208016963"
      "6b65722e436f6e746163745069636b6572526f7756697369746f72080161636563617374"
      "2e6576656e742e6d6f64656c2e466163656361737450726f6d6f4576656e742444657365"
      "7269616c697a657208016e737069726174696f6e2e617661746172732e496e7370697261"
      "74696f6e417661746172734261636b67726f756e64546f70426172436f6e74726f6c6c65"
      "722433080165796672616d65732e6465636f6465722e69636f6e732e49636f6e446f6375"
      "6d656e74244b4653697a6508016f636174696f6e2e706c6174666f726d2e6170692e4c6f"
      "636174696f6e5265717565737408016573736167696e672e100362631c08017573696e65"
      "73732e637573746f6d6572666565646261636b2e6d6f64656c2e437573746f6d65724665"
      "65646261636b506167654461746108017573746f6d746872656164732e6d6f64656c2e54"
      "68726561645468656d65496e666f0801617469766574656d706c617465732e66622e6163"
      "74696f6e2e6576656e746f70656e2e46424576656e744f70656e416374696f6e08017074"
      "69632e7574696c2e45786966526561646572080110036168240a01100367796609016573"
      "2e636f6d6d6f6e2e7265717565737474696d652e63616c656e6461722e636f6d706f6e65"
      "6e74732e536572766963657350726f66696c6550696374757265436f6d706f6e656e7408"
      "016d656e74732e636865636b6f75742e636f6e66696775726174696f6e2e6d6f64656c2e"
      "436865636b6f75745465726d73416e64506f6c696369657308016f746f732e616c62756d"
      "732e667261676d656e742e416c62756d4d656469615069636b6572436f6e74726f6c6c65"
      "72080174632e6c6f6767696e672e6170692e696e74657266616365732e5274634e6f7469"
      "6669636174696f6e496d7072657373696f6e4c6f670801746f72656c6f6361746f722e53"
      "746f72654c6f6361746f724361726450726f766964657224320801696d656c696e652e67"
      "656d73746f6e652e6f7665726c61792e4c6f6767696e674f7665726c6179416461707465"
      "72244c6f6767696e674f7665726c61794974656d56696577486f6c646572080161792e6d"
      "73632e6c69737473656374696f6e2e6974656d2e636f6e74726f6c6c65722e4469766964"
      "65724974656d446174614d6f64656c0801");
}

static std::vector<std::string> buildSubtree(const std::string& prefix,
                                             char seed,
                                             int size) {
  std::vector<std::string> names;
  for (int c = (unsigned char)seed; size > 0; size--, c++) {
    names.push_back(prefix + c);
  }

  return names;
}

TEST_F(StringTreeTest, testSubtreeOfDifferentSize) {
  char seed = 33;
  int max_char_count = 63;
  std::vector<std::string> names =
      buildSubtree("com.", seed, max_char_count - 1);
  int size = 1;
  // construct subtree of different sizes.
  std::vector<std::string> tmp;
  for (const auto& s : names) {
    if (size >= max_char_count) {
      continue;
    }
    auto subtree = buildSubtree(s, seed, size++);
    tmp.insert(tmp.end(), subtree.begin(), subtree.end());
  }
  names.insert(names.end(), tmp.begin(), tmp.end());

  std::string encoded = StringTreeSet::encode_string_tree_set(names);

  std::string hex = toHexRepresentation(encoded);

  std::cout << hex << "\n";

  EXPECT_EQ(
      hex,
      "636f6d2e103f2122030301230e0301241f03012536030126530301277603012820040129"
      "4f04012a0505012b4005012c0206012d4906012e1707012f6a0701304408013124090132"
      "0a0a0133750a0134670b01355f0c01365d0d0137610e01386b0f01397b10013a1212013b"
      "2e13013c5014013d7815013e2717013f5b180140161a0141561b01421d1d0143691e0144"
      "3c200145152201467323014758250148432701493429014a2b2b014b282d014c2b2f014d"
      "3431014e4333014f5835015073370151153a01523c3c0153693e01541d41015556430156"
      "164601575b480158274b0159784d015a5050015b2e53015c1256015d7b58015e6b5b0108"
      "02210801080321220c030108010801080421221b0301231d030108010801080108052122"
      "30030123320301243403010801080108010801080621224b0301234d0301244f03012551"
      "030108010801080108010801080721226c0301236e030124700301257203012674030108"
      "0108010801080108010801080821221404012316040124180401251a0401261c0401271e"
      "040108010801080108010801080108010809212241040123430401244504012547040126"
      "490401274b0401284d040108010801080108010801080108010801080a21227404012376"
      "040124780401257a0401267c0401277e0401280105012903050108010801080108010801"
      "0801080108010801080b21222e0501233005012432050125340501263605012738050128"
      "3a0501293c05012a3e05010801080108010801080108010801080108010801080c21226d"
      "0501236f05012471050125730501267505012777050128790501297b05012a7d05012b7f"
      "050108010801080108010801080108010801080108010801080d21223306012335060124"
      "37060125390601263b0601273d0601283f0601294106012a4306012b4506012c47060108"
      "0108010801080108010801080108010801080108010801080e21227e0601230107012403"
      "0701250507012607070127090701280b0701290d07012a0f07012b1107012c1307012d15"
      "07010801080108010801080108010801080108010801080108010801080f212250070123"
      "520701245407012556070126580701275a0701285c0701295e07012a6007012b6207012c"
      "6407012d6607012e68070108010801080108010801080108010801080108010801080108"
      "01080108102122280801232a0801242c0801252e08012630080127320801283408012936"
      "08012a3808012b3a08012c3c08012d3e08012e4008012f42080108010801080108010801"
      "08010801080108010801080108010801080108010811212206090123080901240a090125"
      "0c0901260e09012710090128120901291409012a1609012b1809012c1a09012d1c09012e"
      "1e09012f2009013022090108010801080108010801080108010801080108010801080108"
      "0108010801080108122122690901236b0901246d0901256f090126710901277309012875"
      "0901297709012a7909012b7b09012c7d09012d7f09012e020a012f040a0130060a013108"
      "0a0108010801080108010801080108010801080108010801080108010801080108010801"
      "08132122530a0123550a0124570a0125590a01265b0a01275d0a01285f0a0129610a012a"
      "630a012b650a012c670a012d690a012e6b0a012f6d0a01306f0a0131710a0132730a0108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "142122430b0123450b0124470b0125490b01264b0b01274d0b01284f0b0129510b012a53"
      "0b012b550b012c570b012d590b012e5b0b012f5d0b01305f0b0131610b0132630b013365"
      "0b0108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108152122390c01233b0c01243d0c01253f0c0126410c0127430c0128450c0129"
      "470c012a490c012b4b0c012c4d0c012d4f0c012e510c012f530c0130550c0131570c0132"
      "590c01335b0c01345d0c0108010801080108010801080108010801080108010801080108"
      "01080108010801080108010801080108162122350d0123370d0124390d01253b0d01263d"
      "0d01273f0d0128410d0129430d012a450d012b470d012c490d012d4b0d012e4d0d012f4f"
      "0d0130510d0131530d0132550d0133570d0134590d01355b0d0108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108172122"
      "370e0123390e01243b0e01253d0e01263f0e0127410e0128430e0129450e012a470e012b"
      "490e012c4b0e012d4d0e012e4f0e012f510e0130530e0131550e0132570e0133590e0134"
      "5b0e01355d0e01365f0e0108010801080108010801080108010801080108010801080108"
      "01080108010801080108010801080108010801081821223f0f0123410f0124430f012545"
      "0f0126470f0127490f01284b0f01294d0f012a4f0f012b510f012c530f012d550f012e57"
      "0f012f590f01305b0f01315d0f01325f0f0133610f0134630f0135650f0136670f013769"
      "0f0108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801081921224d1001234f100124511001255310012655100127"
      "57100128591001295b10012a5d10012b5f10012c6110012d6310012e6510012f67100130"
      "691001316b1001326d1001336f1001347110013573100136751001377710013879100108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "0108010801080108010801081a212261110123631101246511012567110126691101276b"
      "1101286d1101296f11012a7111012b7311012c7511012d7711012e7911012f7b1101307d"
      "1101317f110132021201330412013406120135081201360a1201370c1201380e12013910"
      "120108010801080108010801080108010801080108010801080108010801080108010801"
      "08010801080108010801080108010801081b21227b1201237d1201247f12012502130126"
      "0413012706130128081301290a13012a0c13012b0e13012c1013012d1213012e1413012f"
      "16130130181301311a1301321c1301331e13013420130135221301362413013726130138"
      "281301392a13013a2c130108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801081c21221c1401231e"
      "14012420140125221401262414012726140128281401292a14012a2c14012b2e14012c30"
      "14012d3214012e3414012f36140130381401313a1401323c1401333e1401344014013542"
      "1401364414013746140138481401394a14013a4c14013b4e140108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108010801081d2122421501234415012446150125481501264a1501274c150128"
      "4e1501295015012a5215012b5415012c5615012d5815012e5a15012f5c1501305e150131"
      "60150132621501336415013466150135681501366a1501376c1501386e1501397015013a"
      "7215013b7415013c76150108010801080108010801080108010801080108010801080108"
      "01080108010801080108010801080108010801080108010801080108010801081e21226e"
      "16012370160124721601257416012676160127781601287a1601297c16012a7e16012b01"
      "17012c0317012d0517012e0717012f091701300b1701310d1701320f1701331117013413"
      "1701351517013617170137191701381b1701391d17013a1f17013b2117013c2317013d25"
      "170108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801081f21222118012323180124"
      "2518012527180126291801272b1801282d1801292f18012a3118012b3318012c3518012d"
      "3718012e3918012f3b1801303d1801313f18013241180133431801344518013547180136"
      "491801374b1801384d1801394f18013a5118013b5318013c5518013d5718013e59180108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108202122591901235b1901245d"
      "1901255f1901266119012763190128651901296719012a6919012b6b19012c6d19012d6f"
      "19012e7119012f731901307519013177190132791901337b1901347d1901357f19013602"
      "1a0137041a0138061a0139081a013a0a1a013b0c1a013c0e1a013d101a013e121a013f14"
      "1a0108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108010801080108010801080108010801080108010801080108212122181b0123"
      "1a1b01241c1b01251e1b0126201b0127221b0128241b0129261b012a281b012b2a1b012c"
      "2c1b012d2e1b012e301b012f321b0130341b0131361b0132381b01333a1b01343c1b0135"
      "3e1b0136401b0137421b0138441b0139461b013a481b013b4a1b013c4c1b013d4e1b013e"
      "501b013f521b0140541b0108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801082221225c1c01235e1c0124601c0125621c0126641c0127661c0128681c01296a"
      "1c012a6c1c012b6e1c012c701c012d721c012e741c012f761c0130781c01317a1c01327c"
      "1c01337e1c0134011d0135031d0136051d0137071d0138091d01390b1d013a0d1d013b0f"
      "1d013c111d013d131d013e151d013f171d0140191d01411b1d0108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108232122271e0123291e01242b1e0125"
      "2d1e01262f1e0127311e0128331e0129351e012a371e012b391e012c3b1e012d3d1e012e"
      "3f1e012f411e0130431e0131451e0132471e0133491e01344b1e01354d1e01364f1e0137"
      "511e0138531e0139551e013a571e013b591e013c5b1e013d5d1e013e5f1e013f611e0140"
      "631e0141651e0142671e0108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "0108010801080108242122771f0123791f01247b1f01257d1f01267f1f01270220012804"
      "2001290620012a0820012b0a20012c0c20012d0e20012e1020012f122001301420013116"
      "200132182001331a2001341c2001351e2001362020013722200138242001392620013a28"
      "20013b2a20013c2c20013d2e20013e3020013f322001403420014136200142382001433a"
      "200108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "082521224e21012350210124522101255421012656210127582101285a2101295c21012a"
      "5e21012b6021012c6221012d6421012e6621012f682101306a2101316c2101326e210133"
      "70210134722101357421013676210137782101387a2101397c21013a7e21013b0122013c"
      "0322013d0522013e0722013f092201400b2201410d2201420f2201431122014413220108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "2621222b2301232d2301242f230125312301263323012735230128372301293923012a3b"
      "23012b3d23012c3f23012d4123012e4323012f4523013047230131492301324b2301334d"
      "2301344f230135512301365323013755230138572301395923013a5b23013b5d23013c5f"
      "23013d6123013e6323013f6523014067230141692301426b2301436d2301446f23014571"
      "230108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "08010801082721220e25012310250124122501251425012616250127182501281a250129"
      "1c25012a1e25012b2025012c2225012d2425012e2625012f282501302a2501312c250132"
      "2e25013330250134322501353425013636250137382501383a2501393c25013a3e25013b"
      "4025013c4225013d4425013e4625013f482501404a2501414c2501424e25014350250144"
      "522501455425014656250108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "0108010801080108010801080108010828212276260123782601247a2601257c2601267e"
      "26012701270128032701290527012a0727012b0927012c0b27012d0d27012e0f27012f11"
      "270130132701311527013217270133192701341b2701351d2701361f2701372127013823"
      "2701392527013a2727013b2927013c2b27013d2d27013e2f27013f312701403327014135"
      "27014237270143392701443b2701453d2701463f27014741270108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108292122"
      "6528012367280124692801256b2801266d2801276f280128712801297328012a7528012b"
      "7728012c7928012d7b28012e7d28012f7f28013002290131042901320629013308290134"
      "0a2901350c2901360e29013710290138122901391429013a1629013b1829013c1a29013d"
      "1c29013e1e29013f20290140222901412429014226290143282901442a2901452c290146"
      "2e2901473029014832290108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "01080108010801080108010801080108010801082a21225a2a01235c2a01245e2a012560"
      "2a0126622a0127642a0128662a0129682a012a6a2a012b6c2a012c6e2a012d702a012e72"
      "2a012f742a0130762a0131782a01327a2a01337c2a01347e2a0135012b0136032b013705"
      "2b0138072b0139092b013a0b2b013b0d2b013c0f2b013d112b013e132b013f152b014017"
      "2b0141192b01421b2b01431d2b01441f2b0145212b0146232b0147252b0148272b014929"
      "2b0108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801082b2122552c0123572c0124592c01255b2c01265d2c0127"
      "5f2c0128612c0129632c012a652c012b672c012c692c012d6b2c012e6d2c012f6f2c0130"
      "712c0131732c0132752c0133772c0134792c01357b2c01367d2c01377f2c0138022d0139"
      "042d013a062d013b082d013c0a2d013d0c2d013e0e2d013f102d0140122d0141142d0142"
      "162d0143182d01441a2d01451c2d01461e2d0147202d0148222d0149242d014a262d0108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "0108010801080108010801082c2122562e0123582e01245a2e01255c2e01265e2e012760"
      "2e0128622e0129642e012a662e012b682e012c6a2e012d6c2e012e6e2e012f702e013072"
      "2e0131742e0132762e0133782e01347a2e01357c2e01367e2e0137012f0138032f013905"
      "2f013a072f013b092f013c0b2f013d0d2f013e0f2f013f112f0140132f0141152f014217"
      "2f0143192f01441b2f01451d2f01461f2f0147212f0148232f0149252f014a272f014b29"
      "2f0108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "08010801080108010801080108010801082d21225d3001235f3001246130012563300126"
      "6530012767300128693001296b30012a6d30012b6f30012c7130012d7330012e7530012f"
      "77300130793001317b3001327d3001337f30013402310135043101360631013708310138"
      "0a3101390c31013a0e31013b1031013c1231013d1431013e1631013f183101401a310141"
      "1c3101421e31014320310144223101452431014626310147283101482a3101492c31014a"
      "2e31014b3031014c32310108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801082e21226a3201236c"
      "3201246e320125703201267232012774320128763201297832012a7a32012b7c32012c7e"
      "32012d0133012e0333012f0533013007330131093301320b3301330d3301340f33013511"
      "3301361333013715330138173301391933013a1b33013b1d33013c1f33013d2133013e23"
      "33013f2533014027330141293301422b3301432d3301442f330145313301463333014735"
      "330148373301493933014a3b33014b3d33014c3f33014d41330108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108010801082f21227d3401237f34012402350125043501260635012708350128"
      "0a3501290c35012a0e35012b1035012c1235012d1435012e1635012f183501301a350131"
      "1c3501321e35013320350134223501352435013626350137283501382a3501392c35013a"
      "2e35013b3035013c3235013d3435013e3635013f383501403a3501413c3501423e350143"
      "40350144423501454435014646350147483501484a3501494c35014a4e35014b5035014c"
      "5235014d5435014e56350108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010830212217"
      "370123193701241b3701251d3701261f37012721370128233701292537012a2737012b29"
      "37012c2b37012d2d37012e2f37012f31370130333701313537013237370133393701343b"
      "3701353d3701363f37013741370138433701394537013a4737013b4937013c4b37013d4d"
      "37013e4f37013f51370140533701415537014257370143593701445b3701455d3701465f"
      "37014761370148633701496537014a6737014b6937014c6b37014d6d37014e6f37014f71"
      "370108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801083121223639012338390124"
      "3a3901253c3901263e39012740390128423901294439012a4639012b4839012c4a39012d"
      "4c39012e4e39012f50390130523901315439013256390133583901345a3901355c390136"
      "5e39013760390138623901396439013a6639013b6839013c6a39013d6c39013e6e39013f"
      "70390140723901417439014276390143783901447a3901457c3901467e390147013a0148"
      "033a0149053a014a073a014b093a014c0b3a014d0d3a014e0f3a014f113a0150133a0108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "0108010801080108010801080108010801080108010801083221225b3b01235d3b01245f"
      "3b0125613b0126633b0127653b0128673b0129693b012a6b3b012b6d3b012c6f3b012d71"
      "3b012e733b012f753b0130773b0131793b01327b3b01337d3b01347f3b0135023c013604"
      "3c0137063c0138083c01390a3c013a0c3c013b0e3c013c103c013d123c013e143c013f16"
      "3c0140183c01411a3c01421c3c01431e3c0144203c0145223c0146243c0147263c014828"
      "3c01492a3c014a2c3c014b2e3c014c303c014d323c014e343c014f363c0150383c01513a"
      "3c0108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108010801080108010801080108010801080108010801080108332122073e0123"
      "093e01240b3e01250d3e01260f3e0127113e0128133e0129153e012a173e012b193e012c"
      "1b3e012d1d3e012e1f3e012f213e0130233e0131253e0132273e0133293e01342b3e0135"
      "2d3e01362f3e0137313e0138333e0139353e013a373e013b393e013c3b3e013d3d3e013e"
      "3f3e013f413e0140433e0141453e0142473e0143493e01444b3e01454d3e01464f3e0147"
      "513e0148533e0149553e014a573e014b593e014c5b3e014d5d3e014e5f3e014f613e0150"
      "633e0151653e0152673e0108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "01080108342122384001233a4001243c4001253e40012640400127424001284440012946"
      "40012a4840012b4a40012c4c40012d4e40012e5040012f52400130544001315640013258"
      "4001335a4001345c4001355e4001366040013762400138644001396640013a6840013b6a"
      "40013c6c40013d6e40013e7040013f724001407440014176400142784001437a4001447c"
      "4001457e4001460141014703410148054101490741014a0941014b0b41014c0d41014d0f"
      "41014e1141014f134101501541015117410152194101531b410108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108010801080108010801080108010801083521226f4201237142012473420125"
      "7542012677420127794201287b4201297d42012a7f42012b0243012c0443012d0643012e"
      "0843012f0a4301300c4301310e4301321043013312430134144301351643013618430137"
      "1a4301381c4301391e43013a2043013b2243013c2443013d2643013e2843013f2a430140"
      "2c4301412e43014230430143324301443443014536430146384301473a4301483c430149"
      "3e43014a4043014b4243014c4443014d4643014e4843014f4a4301504c4301514e430152"
      "504301535243015454430108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "01080108010801083621222d4501232f4501243145012533450126354501273745012839"
      "4501293b45012a3d45012b3f45012c4145012d4345012e4545012f47450130494501314b"
      "4501324d4501334f45013451450135534501365545013757450138594501395b45013a5d"
      "45013b5f45013c6145013d6345013e6545013f67450140694501416b4501426d4501436f"
      "45014471450145734501467545014777450148794501497b45014a7d45014b7f45014c02"
      "46014d0446014e0646014f084601500a4601510c4601520e460153104601541246015514"
      "460108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "0837212270470123724701247447012576470126784701277a4701287c4701297e47012a"
      "0148012b0348012c0548012d0748012e0948012f0b4801300d4801310f48013211480133"
      "134801341548013517480136194801371b4801381d4801391f48013a2148013b2348013c"
      "2548013d2748013e2948013f2b4801402d4801412f480142314801433348014435480145"
      "37480146394801473b4801483d4801493f48014a4148014b4348014c4548014d4748014e"
      "4948014f4b4801504d4801514f4801525148015353480154554801555748015659480108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "3821223a4a01233c4a01243e4a0125404a0126424a0127444a0128464a0129484a012a4a"
      "4a012b4c4a012c4e4a012d504a012e524a012f544a0130564a0131584a01325a4a01335c"
      "4a01345e4a0135604a0136624a0137644a0138664a0139684a013a6a4a013b6c4a013c6e"
      "4a013d704a013e724a013f744a0140764a0141784a01427a4a01437c4a01447e4a014501"
      "4b0146034b0147054b0148074b0149094b014a0b4b014b0d4b014c0f4b014d114b014e13"
      "4b014f154b0150174b0151194b01521b4b01531d4b01541f4b0155214b0156234b015725"
      "4b0108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "08010801083921220a4d01230c4d01240e4d0125104d0126124d0127144d0128164d0129"
      "184d012a1a4d012b1c4d012c1e4d012d204d012e224d012f244d0130264d0131284d0132"
      "2a4d01332c4d01342e4d0135304d0136324d0137344d0138364d0139384d013a3a4d013b"
      "3c4d013c3e4d013d404d013e424d013f444d0140464d0141484d01424a4d01434c4d0144"
      "4e4d0145504d0146524d0147544d0148564d0149584d014a5a4d014b5c4d014c5e4d014d"
      "604d014e624d014f644d0150664d0151684d01526a4d01536c4d01546e4d0155704d0156"
      "724d0157744d0158764d0108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801083a21225f4f0123614f0124634f0125654f012667"
      "4f0127694f01286b4f01296d4f012a6f4f012b714f012c734f012d754f012e774f012f79"
      "4f01307b4f01317d4f01327f4f0133025001340450013506500136085001370a5001380c"
      "5001390e50013a1050013b1250013c1450013d1650013e1850013f1a5001401c5001411e"
      "50014220500143225001442450014526500146285001472a5001482c5001492e50014a30"
      "50014b3250014c3450014d3650014e3850014f3a5001503c5001513e5001524050015342"
      "5001544450015546500156485001574a5001584c5001594e500108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "0801080108010801080108010801080108010801080108010801080108010801083b2122"
      "3b5201233d5201243f520125415201264352012745520128475201294952012a4b52012b"
      "4d52012c4f52012d5152012e5352012f5552013057520131595201325b5201335d520134"
      "5f520135615201366352013765520138675201396952013a6b52013b6d52013c6f52013d"
      "7152013e7352013f7552014077520141795201427b5201437d5201447f52014502530146"
      "0453014706530148085301490a53014a0c53014b0e53014c1053014d1253014e1453014f"
      "16530150185301511a5301521c5301531e53015420530155225301562453015726530158"
      "285301592a53015a2c530108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "01080108010801080108010801080108010801083c21221d5501231f5501242155012523"
      "5501262555012727550128295501292b55012a2d55012b2f55012c3155012d3355012e35"
      "55012f37550130395501313b5501323d5501333f55013441550135435501364555013747"
      "550138495501394b55013a4d55013b4f55013c5155013d5355013e5555013f5755014059"
      "5501415b5501425d5501435f55014461550145635501466555014767550148695501496b"
      "55014a6d55014b6f55014c7155014d7355014e7555014f77550150795501517b5501527d"
      "5501537f550154025601550456015606560157085601580a5601590c56015a0e56015b10"
      "560108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801083d21220558012307580124095801250b5801260d580127"
      "0f580128115801291358012a1558012b1758012c1958012d1b58012e1d58012f1f580130"
      "21580131235801322558013327580134295801352b5801362d5801372f58013831580139"
      "3358013a3558013b3758013c3958013d3b58013e3d58013f3f5801404158014143580142"
      "4558014347580144495801454b5801464d5801474f580148515801495358014a5558014b"
      "5758014c5958014d5b58014e5d58014f5f58015061580151635801526558015367580154"
      "695801556b5801566d5801576f580158715801597358015a7558015b7758015c79580108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "0108010801080108010801083e2122725a0123745a0124765a0125785a01267a5a01277c"
      "5a01287e5a0129015b012a035b012b055b012c075b012d095b012e0b5b012f0d5b01300f"
      "5b0131115b0132135b0133155b0134175b0135195b01361b5b01371d5b01381f5b013921"
      "5b013a235b013b255b013c275b013d295b013e2b5b013f2d5b01402f5b0141315b014233"
      "5b0143355b0144375b0145395b01463b5b01473d5b01483f5b0149415b014a435b014b45"
      "5b014c475b014d495b014e4b5b014f4d5b01504f5b0151515b0152535b0153555b015457"
      "5b0155595b01565b5b01575d5b01585f5b0159615b015a635b015b655b015c675b015d69"
      "5b0108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "080108010801080108010801080108010801080108010801080108010801080108010801"
      "08010801080108010801080108010801083f2122665d0123685d01246a5d01256c5d0126"
      "6e5d0127705d0128725d0129745d012a765d012b785d012c7a5d012d7c5d012e7e5d012f"
      "015e0130035e0131055e0132075e0133095e01340b5e01350d5e01360f5e0137115e0138"
      "135e0139155e013a175e013b195e013c1b5e013d1d5e013e1f5e013f215e0140235e0141"
      "255e0142275e0143295e01442b5e01452d5e01462f5e0147315e0148335e0149355e014a"
      "375e014b395e014c3b5e014d3d5e014e3f5e014f415e0150435e0151455e0152475e0153"
      "495e01544b5e01554d5e01564f5e0157515e0158535e0159555e015a575e015b595e015c"
      "5b5e015d5d5e015e5f5e0108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801080108010801080108"
      "010801080108010801080108010801080108010801080108010801");
}

TEST_F(StringTreeTest, testSSS) {
  std::string encoded = StringTreeSet::encode_string_tree_set({"sss"});

  std::string hex = toHexRepresentation(encoded);

  std::cout << hex << "\n";
  EXPECT_EQ(hex, "7373730801");
}

TEST_F(StringTreeTest, testMapWithValues) {
  auto encoded = StringTreeMap<int16_t>::encode_string_tree_map(
      {{"aaa", 900}, {"aba", 1584}});
  std::string hex = toHexRepresentation(encoded);
  std::cerr << hex << "\n";
  EXPECT_EQ(hex, "61100361620e01016102444e016102705801");
}

TEST_F(StringTreeTest, testFullMapWithValues) {
  auto encoded = StringTreeMap<int16_t>::encode_string_tree_map(
      {{"aaa", 32003}, {"aba", 144},   {"aca", 1053},  {"ada", 1961},
       {"aea", 2870},  {"afa", 3778},  {"aga", 4687},  {"aha", 5596},
       {"aia", 6504},  {"aja", 7413},  {"aka", 8321},  {"ala", 9230},
       {"ama", 10139}, {"ana", 11047}, {"aoa", 11956}, {"apa", 12864},
       {"aqa", 13773}, {"ara", 14682}, {"asa", 15590}, {"ata", 16499},
       {"aua", 17408}, {"ava", 18316}, {"awa", 19225}, {"axa", 20133},
       {"aya", 21042}, {"aza", 21951}, {"aAa", 22859}, {"aBa", 23768},
       {"aCa", 24676}, {"aDa", 25585}, {"aEa", 26494}, {"aFa", 27402},
       {"aGa", 28311}, {"aHa", 29220}, {"aIa", 30128}, {"aJa", 31037},
       {"aKa", 31945}, {"aLa", 86},    {"aMa", 995},   {"aNa", 1903},
       {"aOa", 2812},  {"aPa", 3720},  {"aQa", 4629},  {"aRa", 5538},
       {"aSa", 6446},  {"aTa", 7355},  {"aUa", 8263},  {"aVa", 9172},
       {"aWa", 10081}, {"aXa", 10989}, {"aYa", 11898}, {"aZa", 12807},
       {"a0a", 13715}, {"a1a", 14624}, {"a2a", 15532}, {"a3a", 16441},
       {"a4a", 17350}, {"a5a", 18258}, {"a6a", 19167}, {"a7a", 20075},
       {"a8a", 20984}, {"a9a", 21893}, {"a_a", 22801}, {"a$a", 543},
       {"a.a", 11089}});
  std::string hex = toHexRepresentation(encoded);
  std::cerr << hex << "\n";
  EXPECT_EQ(
      hex,
      "611042242e0c03013012030131180301321e030133240301342a03013530030136360301"
      "373c03013842030139480301414e030142540301435a03014460030145660301466c0301"
      "4772030148780301497e03014a0504014b0b04014c1104014d1604014e1b04014f200401"
      "50250401512a04015230040153360401543c04015542040156480401574e040158540401"
      "595a04015a6004015f660401616c04016272040163770401647c04016502050166070501"
      "670c050168120501691805016a1e05016b2405016c2a05016d3005016e3605016f3c0501"
      "7042050171480501724e050173540501745a05017560050176660501776c050178720501"
      "797805017a7e050161025f48016103516d420161035356430161036064430161036c7243"
      "016103794044016103464f44016103525d440161035f6b440161036b7944016103784745"
      "0161034556450161034b6545016103587345016103644146016103714f460161037e5d46"
      "0161034a6c46016103577a460161036448470161037056470161037d6447016103497347"
      "0161025641016102634f0161026f5d0161027c6b016102487a0161035548410161036256"
      "410161036e64410161037b7241016103474142016103544f42016103615d420161036d6b"
      "420161037a794201610347484301610351644501610343744701610250420161025d5001"
      "6102695e016102766c016102427b0161034f49410161035c574101610368654101610375"
      "73410161034142420161034e50420161035b5e42016103676c42016103747a4201610340"
      "49430161034d57430161035a65430161036673430161037341440161034050440161034c"
      "5e44016103596c44016103657a440161037248450161037f564501");
}

TEST_F(StringTreeTest, testTheLimits) {
  auto encoded = StringTreeMap<int32_t>::encode_string_tree_map(
      {{"xyz", 2147483647}, {"xx", -2147483648}, {"y", -1}, {"yy", 0}});
  std::string hex = toHexRepresentation(encoded);
  std::cerr << hex << "\n";
  EXPECT_EQ(hex,
            "100378792001011003787917010106404040404042017a067f7f7f7f7f4101067f"
            "7f7f7f7f4302790801");
}

TEST_F(StringTreeTest, testVariableLengthPayloads) {
  auto encoded =
      StringTreeMap<int32_t>::encode_string_tree_map({{"ab", 63},
                                                      {"abc", 64},
                                                      {"abcd", 65},
                                                      {"xy", 4095},
                                                      {"xyz", 4096},
                                                      {"xyzz", 4097}});
  std::string hex = toHexRepresentation(encoded);
  std::cerr << hex << "\n";
  EXPECT_EQ(hex,
            "1003617816010162017f026302404102640241410179027f7f027a03404041027a"
            "0341404101");
}

TEST_F(StringTreeTest, testStringToString) {
  auto encoded = StringTreeStringMap::encode_string_tree_map(
      {{"ab", "one"}, {"abc", "two"}});
  std::string hex = toHexRepresentation(encoded);
  EXPECT_EQ(hex, "0701010f010161620802630146010401016f6e6504010174776f");
}

TEST_F(StringTreeTest, testStringToStringWithJavaSurrogatePairs) {
  auto hello_world_mutf8 =
      resources::convert_utf8_to_mutf8(u8"Hello, \U0001F30E!");

  auto encoded = StringTreeStringMap::encode_string_tree_map(
      {{"ab", "one"}, {"abc", "two"}, {"another", hello_world_mutf8}});
  std::string hex = toHexRepresentation(encoded);
  EXPECT_EQ(hex,
            "0701011d0101611003626e0f01010802630146016f74686572014c010401016f6e"
            "6504010174776f0b010148656c6c6f2c20ffffffedffffffa0ffffffbcffffffed"
            "ffffffbcffffff8e21");
}

TEST_F(StringTreeTest, testStringToStringWithComplexStrings) {
  auto encoded =
      StringTreeStringMap::encode_string_tree_map({{"ONE", "one"},
                                                   {"ONE_V0", "one_v0"},
                                                   {"TWO", "two"},
                                                   {"THREE", "three"},
                                                   {"FOUR", "(parentheses)"},
                                                   {"FIVE", "::,"},
                                                   {"SIX", "dash-"}});
  std::string hex = toHexRepresentation(encoded);
  EXPECT_EQ(hex,
            "0701014701011005464f200101532b0101543001011003494f1b01015645080155"
            "520146014e450156025f5630015c014958016501100348573d0101524545016d01"
            "4f0175010401013a3a2c0e010128706172656e746865736573290401016f6e6507"
            "01016f6e655f7630060101646173682d060101746872656504010174776f");
}
